The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to structures and methods for implementing user circuits by combining multiple logic blocks in an FPGA.
Programmable logic devices (PLDs) are a well-known type of digital integrated circuit that may be programmed by a user to perform specified logic functions. One type of PLD, the field programmable gate array (FPGA), typically includes an array of configurable logic elements (CLEs) surrounded by a ring of programmable input/output blocks (IOBs). The CLEs and IOBs are interconnected by a programmable interconnect structure. (The programmable interconnect structure between CLES and IOBs is also referred to as general interconnect). The CLES, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLES, IOBs, and interconnect structure are configured. The configuration data may be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
One significant task when implementing a user circuit in an FPGA is the assignment of user logic into the various CLEs and IOBs. This process includes xe2x80x9cmappingxe2x80x9d, where the user circuit is divided into pieces that will fit into a single CLE, IOB, or a portion thereof, and xe2x80x9cplacementxe2x80x9d, where each mapped piece of logic is assigned to a particular CLE or IOB (or portion thereof) in a particular location on the FPGA. The final step in implementing the circuit is called xe2x80x9croutingxe2x80x9d, where the mapped and placed logic is connected together using the programmable interconnect structure. The mapping, placement, and routing processes are typically performed by computer software, which reads in a description of the user circuit (for example, in the form of a netlist) and provides the bitstream that is used to program the device, as described above.
In practice, each CLE is typically formed from several smaller logic blocks, such as 4-input lookup tables (LUTs). Because each block has a fixed size, and the size of the block is usually fairly small to facilitate the efficient implementation of small logic functions, the implementation of larger user circuits requires the use of several logic blocks. Sometimes these logic blocks can be accommodated within a single CLE, in which case the general interconnect need not be used to connect the blocks. In other cases, the required number of logic blocks is too large for a single CLE. The necessary logic blocks must then be connected using the general interconnect, which is typically slower than connections within a single CLE. Thus, user circuits up to a certain size (i.e., the size that will fit in a single CLE) are typically faster than user circuits of a larger size. Further, user circuits that fit into a single logic block (e.g., a single 4-input LUT) result in the fastest implementations.
Therefore, it is desirable to provide structures and methods for combining two or more logic blocks in such a way as to permit user circuits too large for a single logic block to function at more nearly the same operating speed as user circuits within a single logic block.
The invention provides a configurable logic element (CLE) for a field programmable gate array (FPGA) that includes xe2x80x9cexpandersxe2x80x9d (i.e., configurable connector circuits having two or more functions) that allow for fast signal communication between logic blocks. Expanders allow the configurable interconnection of a plurality of logic blocks, for example, a plurality of Versatile Implementation Modules (VIMs), to form a single logical entity including two or more VIMs (i.e., a xe2x80x9cVIM complexxe2x80x9d) that can implement large user circuits such as PALs, lookup tables, multiplexers, tristate buffers, and memories.
A user circuit requiring two or more logic blocks that is implemented using expanders is significantly faster than other implementations enabled by prior art structures.
In one embodiment, a CLE according to the invention includes four xe2x80x9cslicesxe2x80x9d. Each slice includes two logic blocksxe2x80x94for example, the hybrid LUT/PAL logic elements first described by Wittig et al. in U.S. Pat. No. 6,150,838, entitled xe2x80x9cFPGA Configurable Logic Block With Multi-Purpose Logic/Memory Circuitxe2x80x9d, which is incorporated herein by reference. The combination of Wittig""s hybrid LUT/PAL structure with the novel expanders described herein allows for the construction of both large PALs (spanning multiple VIMs) and large user circuits requiring the combination of many look-up tables (LUTs) with minimal performance degradation. In this embodiment, VIMs can be combined within a single slice, between two or more slices, or even across CLE boundaries, and either vertically, horizontally, or both. Further, while adjacent slices or logic blocks are most commonly combined, non-adjacent elements can also be combined by configuring the expanders to bypass intervening elements.
In another embodiment of the invention, more limited logic blocks are used, such as those comprising only LUT functions or only product term generator functions.
One embodiment includes a configurable logic block having at least two configurable modes. In a first mode, the logic block provides two N-input LUTs having N shared inputs and two separate outputs. The outputs are then combined using an expander to generate an (N+1)-input function. In a second mode, the logic block provides two N-input LUTs having M unshared inputs, where M is less than N. In one embodiment, the logic block includes a third mode, in which it provides a plurality of product term output signals based on the values of the N input signals.